/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package compiler.scanner.dfa;

import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author meemo
 */
public class DFAMinimizer
{
    //~ Instance fields --------------------------------------------------------

    private DFAState      miniStart;
    private DFAState      start;
    private Set<DFAState> dfaStates;

    //~ Constructors -----------------------------------------------------------

    public DFAMinimizer(Set<DFAState> dfaStates, DFAState start)
    {
        this.dfaStates = dfaStates;
        this.start     = start;
        miniStart      = minimize();
    }

    //~ Methods ----------------------------------------------------------------

    public DFAState getMinimizedDFA()
    {
        return miniStart;
    }

    private static Group getAcceptingStates(Group dfaStates)
    {
        Group acceptingStates = new Group();

        for (DFAState state : dfaStates)
        {
            if (state.acceptingState)
            {
                acceptingStates.add(state);
            }
        }

        return acceptingStates;
    }

    private static Group getGroupOf(DFAState value, Partition partition)
    {
        for (Group group : partition)
        {
            if (group.contains(value))
                return group;
        }

        return null;
    }

    private DFAState minimize()
    {
        Group     initialGroup = new Group(dfaStates);

        Partition partition = new Partition();

        Group     acceptingGroup = getAcceptingStates(initialGroup);
        Group     nonAcceptingGroup = new Group(initialGroup);
        nonAcceptingGroup.removeAll(acceptingGroup);

        partition.add(acceptingGroup);
        partition.add(nonAcceptingGroup);

        Partition newPartition = partition;

        do
        {
            partition    = newPartition;

            newPartition = split(partition);
        }
        while (newPartition.size() != partition.size()); // no more groups have been splitted

        // now we should collapse every group into single DFA state...
        Set<DFAState>           allNewStates = new HashSet<DFAState>();

        Map<DFAState, DFAState> oldStateToNewStateMap = new HashMap<DFAState, DFAState>();

        // collapse the equiv classes
        for (Set<DFAState> group : partition)
        {
            // collape this group into single DFA state
            DFAState state = new DFAState(group);
            allNewStates.add(state);

            for (DFAState oldState : group)
                oldStateToNewStateMap.put(oldState, state);
        }

        for (DFAState state : allNewStates)
        {
            state.updateTransitionToEquivStates(oldStateToNewStateMap);
        }

        return oldStateToNewStateMap.get(start);
    }

    private static Partition split(Partition partition)
    {
        Partition ret = new Partition();

        for (Group group : partition)
        {
            Set<Group> splitted = split(group, partition);
            ret.addAll(splitted);
        }

        return ret;
    }

    private static Set<Group> split(Group group, Partition partition)
    {
        Set<Group>                        ret = new HashSet<Group>();

        // split with that all transitions from all the states of this group go to a
        // the same group
        Map<Discriminator, Set<DFAState>> splitted = new HashMap<Discriminator, Set<DFAState>>();

        for (DFAState state : group)
        {
            // all transitions; a charater to gropu, not character to state
            Discriminator targetGroups = new Discriminator(state.acceptingState ? state.token : "");

            for (Map.Entry<Character, DFAState> transition : state.transitions.entrySet())
            {
                Group targetGroup = getGroupOf(transition.getValue(), partition);
                targetGroups.put(transition.getKey(), targetGroup);
            }

            if (splitted.get(targetGroups) == null)
                splitted.put(targetGroups, new HashSet<DFAState>());

            splitted.get(targetGroups).add(state);
        }

        for (Set<DFAState> entry : splitted.values())
        {
            ret.add(new Group(entry));
        }

        return ret;
    }

    //~ Inner Classes ----------------------------------------------------------

    private static class Discriminator extends IdentityHashMap<Character, Group>
    {
        private String token;

        private Discriminator(String token)
        {
            this.token = token;
        }

        @Override
        public boolean equals(Object o)
        {
            // a group can be discriminated by/distinguished the token it accepts
            return super.equals(o) && token.equals(((Discriminator)o).token);
        }

        @Override
        public int hashCode()
        {
            return super.hashCode() + token.hashCode();
        }
    }

    private static class Group extends HashSet<DFAState>
    {
        private Group() {}

        private Group(Set<DFAState> aSet)
        {
            super(aSet);
        }
    }

    private static class Partition extends HashSet<Group> {}
}
